{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Camelcase Matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #two-pointers #string #string-matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #双指针 #字符串 #字符串匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: camelMatch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #驼峰式匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串数组 <code>queries</code>，和一个表示模式的字符串&nbsp;<code>pattern</code>，请你返回一个布尔数组 <code>answer</code> 。只有在待查项&nbsp;<code>queries[i]</code> 与模式串&nbsp;<code>pattern</code> 匹配时，&nbsp;<code>answer[i]</code>&nbsp;才为 <code>true</code>，否则为 <code>false</code>。</p>\n",
    "\n",
    "<p>如果可以将<strong>小写字母</strong>插入模式串&nbsp;<code>pattern</code>&nbsp;得到待查询项&nbsp;<code>query</code>，那么待查询项与给定模式串匹配。可以在任何位置插入每个字符，也可以不插入字符。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>queries = [\"FooBar\",\"FooBarTest\",\"FootBall\",\"FrameBuffer\",\"ForceFeedBack\"], pattern = \"FB\"\n",
    "<strong>输出：</strong>[true,false,true,true,false]\n",
    "<strong>示例：</strong>\n",
    "\"FooBar\" 可以这样生成：\"F\" + \"oo\" + \"B\" + \"ar\"。\n",
    "\"FootBall\" 可以这样生成：\"F\" + \"oot\" + \"B\" + \"all\".\n",
    "\"FrameBuffer\" 可以这样生成：\"F\" + \"rame\" + \"B\" + \"uffer\".</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>queries = [\"FooBar\",\"FooBarTest\",\"FootBall\",\"FrameBuffer\",\"ForceFeedBack\"], pattern = \"FoBa\"\n",
    "<strong>输出：</strong>[true,false,true,false,false]\n",
    "<strong>解释：</strong>\n",
    "\"FooBar\" 可以这样生成：\"Fo\" + \"o\" + \"Ba\" + \"r\".\n",
    "\"FootBall\" 可以这样生成：\"Fo\" + \"ot\" + \"Ba\" + \"ll\".\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>queries = [\"FooBar\",\"FooBarTest\",\"FootBall\",\"FrameBuffer\",\"ForceFeedBack\"], pattern = \"FoBaT\"\n",
    "<strong>输出：</strong>[false,true,false,false,false]\n",
    "<strong>解释： </strong>\n",
    "\"FooBarTest\" 可以这样生成：\"Fo\" + \"o\" + \"Ba\" + \"r\" + \"T\" + \"est\".\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= pattern.length, queries.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= queries[i].length &lt;= 100</code></li>\n",
    "\t<li><code>queries[i]</code> 和 <code>pattern</code> 由英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [camelcase-matching](https://leetcode.cn/problems/camelcase-matching/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [camelcase-matching](https://leetcode.cn/problems/camelcase-matching/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"FooBar\",\"FooBarTest\",\"FootBall\",\"FrameBuffer\",\"ForceFeedBack\"]\\n\"FB\"', '[\"FooBar\",\"FooBarTest\",\"FootBall\",\"FrameBuffer\",\"ForceFeedBack\"]\\n\"FoBa\"', '[\"FooBar\",\"FooBarTest\",\"FootBall\",\"FrameBuffer\",\"ForceFeedBack\"]\\n\"FoBaT\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        n = len(queries)\n",
    "        l, r = ord('A'), ord('Z')\n",
    "        ans = [True] * n\n",
    "\n",
    "        # 划分模式\n",
    "        for i, word in enumerate(queries):\n",
    "            p = 0\n",
    "            for c in word: \n",
    "                if p<len(pattern) and pattern[p] == c: # 如果相同则匹配，指针移动\n",
    "                    p += 1\n",
    "                elif l<=ord(c) and ord(c)<=r: # 如果不相同且为大写字母，匹配失败\n",
    "                    ans[i] =False\n",
    "                    break\n",
    "                else: # 如果不相同且为小写字母， 继续找下一个进行匹配\n",
    "                    continue\n",
    "            if p<len(pattern): ans[i] = False\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries, pattern):\n",
    "        ans = []\n",
    "        m = len(pattern)\n",
    "        for query in queries:\n",
    "            n = len(query)\n",
    "            i, j = 0, 0\n",
    "            match = True  # 假设匹配成功\n",
    "            while i < n and j < m:\n",
    "                if query[i] == pattern[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                elif query[i].islower():\n",
    "                    i += 1\n",
    "                else:\n",
    "                    match = False  # 不匹配\n",
    "                    break\n",
    "            # 如果模式串的所有字符都匹配完，且查询串剩下的字符都是小写字母，则认为匹配成功\n",
    "            if j == m and all(char.islower() for char in query[i:]):\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        res = [True] * len(queries)\n",
    "        for i in range(len(queries)):\n",
    "            idx = 0\n",
    "            for char in queries[i]:\n",
    "                if idx < len(pattern) and char == pattern[idx]:\n",
    "                    idx += 1\n",
    "                elif char.isupper():\n",
    "                    res[i] = False\n",
    "                    break\n",
    "            \n",
    "            if idx < len(pattern):\n",
    "                res[i] = False\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # res = [True] * len(queries)\n",
    "        # for i in range(len(queries)):\n",
    "        #     idx = 0\n",
    "        #     for char in queries[i]:\n",
    "        #         if idx < len(pattern) and pattern[idx] == char:\n",
    "        #             idx += 1\n",
    "                \n",
    "        #         elif char.isupper():\n",
    "        #             res[i] = False\n",
    "        #             break\n",
    "                \n",
    "        #     if idx < len(pattern):\n",
    "        #         res[i] = False\n",
    "        \n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            ptr = 0\n",
    "            tmp = True\n",
    "            for i in range(len(q)):\n",
    "                if ptr < len(pattern) and q[i] == pattern[ptr]:\n",
    "                    ptr += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    if ord('A') <= ord(q[i]) <= ord('Z'):\n",
    "                        tmp = False\n",
    "                        break\n",
    "            if ptr != len(pattern):\n",
    "                tmp = False\n",
    "            ans.append(tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        n = len(queries)\n",
    "        res = [True] * n\n",
    "\n",
    "        for i in range(len(queries)):\n",
    "            p = 0\n",
    "            for c in queries[i]:\n",
    "                if p < len(pattern) and c == pattern[p]:\n",
    "                    p += 1\n",
    "                elif c.isupper():\n",
    "                    res[i] = False\n",
    "                    break\n",
    "            if p < len(pattern):\n",
    "                res[i] = False\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        self.k=len(pattern)\n",
    "        self.s ={'G', 'X', 'B', 'Q', 'I', 'D', 'T', 'U', 'C', 'A', 'M', 'F', 'N', 'W', 'Y', 'Z', 'E', 'S', 'R', 'K', 'V', 'H', 'O', 'P', 'J', 'L'}\n",
    "\n",
    "\n",
    "        def check(a):\n",
    "            i=j=0\n",
    "            n=len(a)\n",
    "            while i<n:\n",
    "                if a[i]==pattern[j]:\n",
    "                    i+=1 \n",
    "                    j+=1\n",
    "                else:\n",
    "                    if a[i] in self.s:\n",
    "                        return False\n",
    "                    i+=1\n",
    "\n",
    "                if j==self.k:\n",
    "                    break\n",
    "            for w in range(i,n):\n",
    "                if a[w] in self.s:\n",
    "                    return False \n",
    "            return j==self.k\n",
    "                \n",
    "\n",
    "        return [check(v) for v in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        n = len(queries)\n",
    "        m = len(pattern)\n",
    "        answer = [True] * n\n",
    "\n",
    "        for i, query in enumerate(queries):\n",
    "            if m > len(query):\n",
    "                answer[i] = False\n",
    "                continue\n",
    "            j = 0\n",
    "            for _, ch in enumerate(query):\n",
    "                if j < m and ch == pattern[j]:\n",
    "                    j += 1\n",
    "                elif ch.isupper():\n",
    "                    answer[i] = False\n",
    "                    break\n",
    "                else:\n",
    "                    continue\n",
    "            if m != j:\n",
    "                answer[i] = False\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        n = len(queries)\n",
    "        m = len(pattern)\n",
    "        answer = [True] * n\n",
    "\n",
    "        for i, query in enumerate(queries):\n",
    "            if m > len(query):\n",
    "                answer[i] = False\n",
    "                continue\n",
    "            j = 0\n",
    "            for _, ch in enumerate(query):\n",
    "                if j < m and ch == pattern[j]:\n",
    "                    j += 1\n",
    "                elif ch.isupper():\n",
    "                    answer[i] = False\n",
    "                    break\n",
    "                else:\n",
    "                    continue\n",
    "            if m != j:\n",
    "                answer[i] = False\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self,):\n",
    "        self.children = dict()\n",
    "        self.isEnd = False\n",
    "    \n",
    "    def insert(self, word: str) -> None:\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            if ch not in cur.children:\n",
    "                cur.children[ch] = Trie()\n",
    "            cur = cur.children[ch]\n",
    "        cur.isEnd = True\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            if not ch.isupper():\n",
    "                if ch not in cur.children:\n",
    "                    continue\n",
    "            else:\n",
    "                if ch not in cur.children:\n",
    "                    return False\n",
    "            cur = cur.children[ch]\n",
    "        return cur.isEnd\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        # lenp = len(pattern)\n",
    "        # def check(s):\n",
    "        #     ls, lp, lens = 0, 0, len(s)\n",
    "        #     while ls < lens and lp < lenp:\n",
    "        #         if s[ls] == pattern[lp]: lp += 1\n",
    "        #         elif s[ls].isupper(): return False\n",
    "        #         ls += 1\n",
    "        #     return lp == lenp and len(list(filter(lambda x: x.isupper(), s[ls:]))) == 0\n",
    "        # return [check(s) for s in queries]\n",
    "        dict_tree = Trie()\n",
    "        dict_tree.insert(pattern)\n",
    "        return [dict_tree.search(query) for query in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self,):\n",
    "        self.children = dict()\n",
    "        self.isEnd = False\n",
    "    \n",
    "    def insert(self, word: str) -> None:\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            if ch not in cur.children:\n",
    "                cur.children[ch] = Trie()\n",
    "            cur = cur.children[ch]\n",
    "        cur.isEnd = True\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            if not ch.isupper():\n",
    "                # 不匹配的小写字母跳过，这个操作很巧妙，不会移动cur\n",
    "                if ch not in cur.children:\n",
    "                    continue\n",
    "            else:\n",
    "                if ch not in cur.children:\n",
    "                    return False\n",
    "            cur = cur.children[ch]\n",
    "        return cur.isEnd\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        # lenp = len(pattern)\n",
    "        # def check(s):\n",
    "        #     ls, lp, lens = 0, 0, len(s)\n",
    "        #     while ls < lens and lp < lenp:\n",
    "        #         if s[ls] == pattern[lp]: lp += 1\n",
    "        #         elif s[ls].isupper(): return False\n",
    "        #         ls += 1\n",
    "        #     return lp == lenp and len(list(filter(lambda x: x.isupper(), s[ls:]))) == 0\n",
    "        # return [check(s) for s in queries]\n",
    "        dict_tree = Trie()\n",
    "        dict_tree.insert(pattern)\n",
    "        return [dict_tree.search(query) for query in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        n = len(queries)\n",
    "        m=len(pattern)\n",
    "        res = [True] * n\n",
    "        for i in range(n):\n",
    "            p = 0\n",
    "            for c in queries[i]:\n",
    "                if p < m and pattern[p] == c:\n",
    "                    p += 1\n",
    "                elif c.isupper():\n",
    "                    res[i] = False\n",
    "                    break\n",
    "            if p < m:\n",
    "                res[i] = False\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        \n",
    "        def if_true(s):\n",
    "            idx = 0\n",
    "            for i in s:\n",
    "                if i==pattern[idx]:\n",
    "                    idx+=1\n",
    "                    s = s.replace(i,\"\",1)\n",
    "                if idx >= len(pattern):\n",
    "                    break\n",
    "            return s.islower() and idx == len(pattern) \n",
    "\n",
    "        res = []\n",
    "        for i in queries:\n",
    "            res.append(if_true(i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self,):\n",
    "        self.children = dict()\n",
    "        self.isEnd = False\n",
    "    \n",
    "    def insert(self, word: str) -> None:\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            if ch not in cur.children:\n",
    "                cur.children[ch] = Trie()\n",
    "            cur = cur.children[ch]\n",
    "        cur.isEnd = True\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            if not ch.isupper():\n",
    "                # 不匹配的小写字母跳过，这个操作很巧妙，不会移动cur\n",
    "                if ch not in cur.children:\n",
    "                    continue\n",
    "            else:\n",
    "                if ch not in cur.children:\n",
    "                    return False\n",
    "            cur = cur.children[ch]\n",
    "        return cur.isEnd\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        # lenp = len(pattern)\n",
    "        # def check(s):\n",
    "        #     ls, lp, lens = 0, 0, len(s)\n",
    "        #     while ls < lens and lp < lenp:\n",
    "        #         if s[ls] == pattern[lp]: lp += 1\n",
    "        #         elif s[ls].isupper(): return False\n",
    "        #         ls += 1\n",
    "        #     return lp == lenp and len(list(filter(lambda x: x.isupper(), s[ls:]))) == 0\n",
    "        # return [check(s) for s in queries]\n",
    "        dict_tree = Trie()\n",
    "        dict_tree.insert(pattern)\n",
    "        return [dict_tree.search(query) for query in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        self.k=len(pattern)\n",
    "        self.s ={'G', 'X', 'B', 'Q', 'I', 'D', 'T', 'U', 'C', 'A', 'M', 'F', 'N', 'W', 'Y', 'Z', 'E', 'S', 'R', 'K', 'V', 'H', 'O', 'P', 'J', 'L'}\n",
    "        def check(a):\n",
    "            x=1\n",
    "            i=j=0\n",
    "            n=len(a)\n",
    "            while i<n:\n",
    "                if a[i]==pattern[j]:\n",
    "                    j+=1\n",
    "                else:\n",
    "                    if a[i] in self.s:\n",
    "                        return False\n",
    "                i+=1\n",
    "                if j==self.k:\n",
    "                    x=0\n",
    "                    break\n",
    "            if x:return False\n",
    "            for w in range(i,n):\n",
    "                if a[w] in self.s:\n",
    "                    return False \n",
    "            return True\n",
    "\n",
    "        return [check(v) for v in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        # 遍历 遍历待查项 比较模式串使用长度\n",
    "        n = len(pattern)\n",
    "        res = []\n",
    "        for s in queries:\n",
    "            i = 0\n",
    "            for c in s:\n",
    "                if i < n and c == pattern[i]:\n",
    "                    i += 1\n",
    "                elif c.islower():\n",
    "                    continue\n",
    "                else:\n",
    "                    res.append(False)\n",
    "                    break\n",
    "            else:\n",
    "                res.append(i == n)\n",
    "        return res\n",
    "\n",
    "        # 正则\n",
    "        s = '(^[a-z]*' + '[a-z]*'.join(list(pattern)) + '[a-z]*$)'\n",
    "        pat = re.compile(s)\n",
    "        res = list(map(pat.match, queries))\n",
    "        return list(map(bool, res))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.children = dict()\n",
    "        self.isEnd = False\n",
    "\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        \"\"\"\n",
    "        Inserts a word into the trie.\n",
    "        \"\"\"\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            if ch not in cur.children:\n",
    "                cur.children[ch] = Trie()\n",
    "            cur = cur.children[ch]\n",
    "        cur.isEnd = True\n",
    "\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        \"\"\"\n",
    "        Returns if the word is in the trie.\n",
    "        \"\"\"\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            if ord(ch) > 96:\n",
    "                if ch not in cur.children:\n",
    "                    continue\n",
    "            else:\n",
    "                if ch not in cur.children:\n",
    "                    return False\n",
    "            cur = cur.children[ch]\n",
    "\n",
    "        return cur is not None and cur.isEnd\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        trie_tree = Trie()\n",
    "        trie_tree.insert(pattern)\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            res.append(trie_tree.search(query))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        \n",
    "        def match(i, j, word):\n",
    "            ## 两个都结束, 代码匹配结束\n",
    "            if i >= len(word) and j>= len(pattern):\n",
    "                return True            \n",
    "            if i >= len(word) and j < len(pattern):\n",
    "                ## 单词结束, pattern还有剩余, 匹配失败\n",
    "                return False\n",
    "            if i < len(word) and j >= len(pattern):\n",
    "                ## pattern接受, 单词还有剩余, 剩下的单词必须全部为小写\n",
    "                return all([v >= 'a' for v in word[i:]])\n",
    "            \n",
    "            if word[i] == pattern[j]:\n",
    "                return match(i+1, j+1, word)\n",
    "            ## 代表是大写\n",
    "            if ord(word[i]) < ord('a'):\n",
    "                return False\n",
    "            return match(i+1, j, word)\n",
    "        \n",
    "        return [match(0, 0, v) for v in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        def check(s, t):\n",
    "            m, n = len(s), len(t)\n",
    "            i = j = 0\n",
    "            while j < n:\n",
    "                while i < m and s[i] != t[j] and s[i].islower():\n",
    "                    i += 1\n",
    "                if i == m or s[i] != t[j]:\n",
    "                    return False\n",
    "                i, j = i + 1, j + 1\n",
    "            while i < m and s[i].islower():\n",
    "                i += 1\n",
    "            return i == m\n",
    "\n",
    "        return [check(q, pattern) for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        n = len(queries)\n",
    "        res = [True] * n\n",
    "        for i in range(n):\n",
    "            idx = 0\n",
    "            for char in queries[i]:\n",
    "                if idx < len(pattern) and char == pattern[idx]:\n",
    "                    idx += 1\n",
    "                elif char.isupper():\n",
    "                    res[i] = False\n",
    "                    break    \n",
    "            \n",
    "            if idx < len(pattern):\n",
    "                res[i] = False\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # res = [True] * len(queries)\n",
    "        # for i in range(len(queries)):\n",
    "        #     idx = 0\n",
    "        #     for char in queries[i]:\n",
    "        #         if idx < len(pattern) and pattern[idx] == char:\n",
    "        #             idx += 1\n",
    "                \n",
    "        #         elif char.isupper():\n",
    "        #             res[i] = False\n",
    "        #             break\n",
    "                \n",
    "        #     if idx < len(pattern):\n",
    "        #         res[i] = False\n",
    "        \n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        def check(s, t):\n",
    "            m, n = len(s), len(t)\n",
    "            i = j = 0\n",
    "            while j < n:\n",
    "                while i < m and s[i] != t[j] and s[i].islower():\n",
    "                    i += 1\n",
    "                if i == m or s[i] != t[j]:\n",
    "                    return False\n",
    "                i, j = i + 1, j + 1\n",
    "            while i < m and s[i].islower():\n",
    "                i += 1\n",
    "            return i == m\n",
    "\n",
    "        return [check(q, pattern) for q in queries]\n",
    "\n",
    "# 作者：ylb\n",
    "# 链接：https://leetcode.cn/problems/camelcase-matching/solutions/2225856/python3javacgotypescript-yi-ti-yi-jie-sh-vr5x/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        def match(x,y):\n",
    "            a,b=0,0\n",
    "            m,n=0,0\n",
    "            for i in x:\n",
    "                if i.isupper():\n",
    "                    m+=1\n",
    "            for i in y:\n",
    "                if i.isupper():\n",
    "                    n+=1\n",
    "            if m!=n:\n",
    "                return False\n",
    "            while a<len(x) and b<len(y):\n",
    "                if x[a]==y[b]:\n",
    "                    b+=1\n",
    "                a+=1\n",
    "            return b==len(y)\n",
    "        arr=[]\n",
    "        for i in queries:\n",
    "            arr.append(match(i,pattern))\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        self.k=len(pattern)\n",
    "        self.s ={'G', 'X', 'B', 'Q', 'I', 'D', 'T', 'U', 'C', 'A', 'M', 'F', 'N', 'W', 'Y', 'Z', 'E', 'S', 'R', 'K', 'V', 'H', 'O', 'P', 'J', 'L'}\n",
    "        def check(a):\n",
    "            x=1\n",
    "            i=j=0\n",
    "            n=len(a)\n",
    "            while i<n:\n",
    "                if a[i]==pattern[j]:\n",
    "                    j+=1\n",
    "                else:\n",
    "                    if a[i] in self.s:return False\n",
    "                i+=1\n",
    "                if j==self.k:\n",
    "                    x=0\n",
    "                    break\n",
    "            if x:return False\n",
    "            for w in range(i,n):\n",
    "                if a[w] in self.s:\n",
    "                    return False \n",
    "            return True\n",
    "\n",
    "        return [check(v) for v in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        n = len(queries)\n",
    "        m=len(pattern)\n",
    "        res = [True] * n\n",
    "        for i in range(n):\n",
    "            p = 0\n",
    "            for c in queries[i]:\n",
    "                if p < m and pattern[p] == c:\n",
    "                    p += 1\n",
    "                elif c.isupper():\n",
    "                    res[i] = False\n",
    "                    break\n",
    "            if p < m:\n",
    "                res[i] = False\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        result = []\n",
    "        for each in queries:\n",
    "            temppattern = pattern\n",
    "            tempresult = True\n",
    "            length = len(temppattern)\n",
    "            for i in range(len(each)):\n",
    "                if length > 0 and each[i] == temppattern[0]:\n",
    "                    temppattern = temppattern[1:]\n",
    "                    length -= 1\n",
    "                elif \"A\" <= each[i] <= \"Z\" and each[i] not in temppattern:\n",
    "                    tempresult = False\n",
    "            if length > 0:\n",
    "                result.append(False)\n",
    "            else:\n",
    "                result.append(tempresult)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        \n",
    "        def check(a,b):\n",
    "            na=len(a)\n",
    "            nb=len(b)\n",
    "            i=0\n",
    "            j=0\n",
    "            while i<na:\n",
    "                if j<nb:\n",
    "                    if a[i]==b[j]:\n",
    "                        j=j+1\n",
    "                    elif a[i].isupper():\n",
    "                        return False\n",
    "                else:\n",
    "                    if a[i].isupper():\n",
    "                        return False\n",
    "                i=i+1\n",
    "            if j==nb:\n",
    "                return True\n",
    "            return False\n",
    "        ans=[0]*len(queries)\n",
    "\n",
    "        for i,v in enumerate(queries):\n",
    "            ans[i]=check(v,pattern)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        m=r\"^[a-z]*\"+r\"[a-z]*\".join(list(pattern))+r\"[a-z]*$\"\n",
    "        return [True if re.match(m,i) else False for i in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        ans = []\n",
    "        for query in queries:\n",
    "            i, j = 0, 0\n",
    "            while i < len(query) and j < len(pattern):\n",
    "                if query[i] == pattern[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                elif 'a' <= query[i] <= 'z':\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "            while i < len(query) and j == len(pattern):\n",
    "                if 'a' <= query[i] <= 'z':\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "            ans.append(j == len(pattern) and i == len(query))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        self.k=len(pattern)\n",
    "        self.s ={'G', 'X', 'B', 'Q', 'I', 'D', 'T', 'U', 'C', 'A', 'M', 'F', 'N', 'W', 'Y', 'Z', 'E', 'S', 'R', 'K', 'V', 'H', 'O', 'P', 'J', 'L'}\n",
    "        def check(a):\n",
    "            x=1\n",
    "            i=j=0\n",
    "            n=len(a)\n",
    "            while i<n:\n",
    "                if a[i]==pattern[j]:\n",
    "                    j+=1\n",
    "                else:\n",
    "                    if a[i] in self.s:return False\n",
    "                i+=1\n",
    "                if j==self.k:\n",
    "                    x=0\n",
    "                    break\n",
    "            if x:return False\n",
    "            for w in range(i,n):\n",
    "                if a[w] in self.s:\n",
    "                    return False \n",
    "            return True\n",
    "\n",
    "        return [check(v) for v in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import string\n",
    "upper = string.ascii_uppercase\n",
    "\n",
    "class Solution:\n",
    "    def match(self,q:str,pat:str)->bool:\n",
    "        if len(q)<len(pat):\n",
    "            return False\n",
    "        i = 0\n",
    "        m = len(q)\n",
    "        for p in pat:\n",
    "            while i<m and q[i]!=p and q[i] not in upper:\n",
    "                i+=1\n",
    "            if i==m:\n",
    "                return False\n",
    "            if (p in upper)!=(q[i] in upper):\n",
    "                return False\n",
    "            i += 1\n",
    "        return not any(c in upper for c in q[i:])\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            res.append(self.match(q, pattern))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        ans,n,a=[],len(pattern),False\n",
    "        for x in queries:\n",
    "          i=0\n",
    "          a=False  \n",
    "          for y in x:\n",
    "            if not a:  \n",
    "               if y.islower():\n",
    "                  if y==pattern[i]:\n",
    "                      i+=1\n",
    "               else:\n",
    "                 if y!=pattern[i]:\n",
    "                     break\n",
    "                 else:\n",
    "                     i+=1\n",
    "            else:\n",
    "               if y.isupper():\n",
    "                   a=False\n",
    "                   break\n",
    "            if i==n:\n",
    "                    a=True                                    \n",
    "          ans.append(a)\n",
    "        return ans              "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        ans = []\n",
    "        for query in queries:\n",
    "            pattern = list(pattern)\n",
    "            p = 0\n",
    "            flag = 1\n",
    "            for c in query:\n",
    "                if p < len(pattern) and pattern[p] == c:\n",
    "                    p += 1\n",
    "                    continue\n",
    "                if c.islower():\n",
    "                    continue\n",
    "                else:\n",
    "                    flag = 0\n",
    "                    break\n",
    "            if flag == 0 or p < len(pattern):\n",
    "                ans.append(False)\n",
    "            else:\n",
    "                ans.append(True)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = dict()\n",
    "        self.isEnd = False\n",
    "    \n",
    "    def insert(self, word):\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            if ch not in cur.children:\n",
    "                cur.children[ch] = Trie()\n",
    "            cur = cur.children[ch]\n",
    "        cur.isEnd = True\n",
    "\n",
    "    def search(self, prefix):\n",
    "        cur = self\n",
    "        for ch in prefix:\n",
    "            if ord(ch) > 96:\n",
    "                if ch not in cur.children:\n",
    "                    continue\n",
    "            else:\n",
    "                if ch not in cur.children:\n",
    "                    return False\n",
    "            cur = cur.children[ch]\n",
    "        return cur is not None and cur.isEnd\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        trie_tree = Trie()\n",
    "        trie_tree.insert(pattern)\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            res.append(trie_tree.search(query))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        lenp = len(pattern)\n",
    "        def check(s):\n",
    "            ls, lp, lens = 0, 0, len(s)\n",
    "            while ls < lens and lp < lenp:\n",
    "                if s[ls] == pattern[lp]: lp += 1\n",
    "                elif s[ls].isupper(): return False\n",
    "                ls += 1\n",
    "            return lp == lenp and len(list(filter(lambda x: x.isupper(), s[ls:]))) == 0\n",
    "\n",
    "        return [check(s) for s in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        def check(word,pattern):\n",
    "            l=0\n",
    "            n=len(pattern)\n",
    "            for i in range(len(word)):\n",
    "                if word[i].isupper() and (l>=n or (l<=n-1 and word[i]!=pattern[l])):\n",
    "                    return False\n",
    "                if l<=n-1 and word[i]==pattern[l]:\n",
    "                    l+=1\n",
    "            return l==n\n",
    "        res=[]\n",
    "        for each in queries:\n",
    "            res.append(check(each,pattern))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        s = re.sub('[^A-Z]','',pattern)\n",
    "        for i in range(len(queries)):\n",
    "            ss = queries[i]\n",
    "            if s == re.sub('[^A-Z]','',ss):\n",
    "                j, f = 0, 1\n",
    "                for k in pattern:\n",
    "                    while k != ss[j]:\n",
    "                        j+=1\n",
    "                        if j == len(ss):\n",
    "                            queries[i] = False\n",
    "                            f=0\n",
    "                            break\n",
    "                    j+=1\n",
    "                    if not(f):break\n",
    "                if f:queries[i] = True\n",
    "            else:\n",
    "                queries[i] = False\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        # 遍历 遍历待查项 比较模式串使用长度\n",
    "        n = len(pattern)\n",
    "        res = []\n",
    "        for s in queries:\n",
    "            i = 0\n",
    "            for c in s:\n",
    "                if i < n and c == pattern[i]:\n",
    "                    i += 1\n",
    "                elif c.islower():\n",
    "                    continue\n",
    "                else:\n",
    "                    res.append(False)\n",
    "                    break\n",
    "            else:\n",
    "                res.append(i == n)\n",
    "        return res\n",
    "\n",
    "        # 正则\n",
    "        s = '(^[a-z]*' + '[a-z]*'.join(list(pattern)) + '[a-z]*$)'\n",
    "        pat = re.compile(s)\n",
    "        res = list(map(pat.match, queries))\n",
    "        return list(map(bool, res))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        n = len(queries)\n",
    "        res = [True]*n\n",
    "        n2 = len(pattern)\n",
    "        for idx,q in enumerate(queries):\n",
    "            i = j = 0\n",
    "            n1 = len(q)\n",
    "            while i<n1 and j<n2:\n",
    "                if q[i] == pattern[j]:\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    if q[i].islower():\n",
    "                        i+=1\n",
    "                    else:\n",
    "                        res[idx] = False\n",
    "                        break\n",
    "            print(i,j,res[idx])\n",
    "            while i<n1:\n",
    "                if q[i].isupper():\n",
    "                    res[idx] = False\n",
    "                    break\n",
    "                i+=1\n",
    "            if j<n2:\n",
    "                res[idx] = False\n",
    "        return res\n",
    "                        \n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        \n",
    "        def check():\n",
    "            i = 0\n",
    "            for w in word:\n",
    "                if i < n and w == pattern[i]:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    if w.isupper():\n",
    "                        return False\n",
    "            return i == n\n",
    "        \n",
    "        n = len(pattern)\n",
    "        ans = []\n",
    "        for word in queries:\n",
    "            ans.append(check())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        # Q = []\n",
    "        # for query in queries:\n",
    "        #     res = \"\"\n",
    "        #     for ch in query:\n",
    "        #         if 65 <= ord(ch) <= 90:\n",
    "        #             res += ch\n",
    "        #     Q.append(res)\n",
    "        # res = []\n",
    "        # for q in Q:\n",
    "        #     if q == pattern:\n",
    "        #         res.append(True)\n",
    "        #     else:\n",
    "        #         res.append(False)\n",
    "        # return res\n",
    "        def check(s, t):\n",
    "            m = len(s)\n",
    "            n = len(t)\n",
    "            i = j = 0\n",
    "            while j < n:\n",
    "                while i < m and s[i] != t[j] and s[i].islower():\n",
    "                    i += 1\n",
    "                if i == m or s[i] != t[j]:\n",
    "                    return False\n",
    "                i, j = i + 1, j + 1\n",
    "            while i < m and s[i].islower():\n",
    "                i += 1\n",
    "            return i == m\n",
    "        return [check(q, pattern) for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        # 遍历 遍历待查项 比较模式串使用长度\n",
    "        n = len(pattern)\n",
    "        res = []\n",
    "        for s in queries:\n",
    "            i = 0\n",
    "            for c in s:\n",
    "                if i < n and c == pattern[i]:\n",
    "                    i += 1\n",
    "                elif c.islower():\n",
    "                    continue\n",
    "                else:\n",
    "                    res.append(False)\n",
    "                    break\n",
    "            else:\n",
    "                res.append(i == n)\n",
    "        return res\n",
    "\n",
    "        # 正则\n",
    "        s = '(^[a-z]*' + '[a-z]*'.join(list(pattern)) + '[a-z]*$)'\n",
    "        pat = re.compile(s)\n",
    "        res = list(map(pat.match, queries))\n",
    "        return list(map(bool, res))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        def check(s, pattern):\n",
    "            m, n = len(s), len(pattern)\n",
    "            i, j = 0, 0\n",
    "            while i < m and j < n:\n",
    "                if s[i] == pattern[j]:\n",
    "                    j += 1\n",
    "                    i += 1\n",
    "                elif i < m:\n",
    "                    if not s[i].islower():\n",
    "                        break\n",
    "                    else:\n",
    "                        i += 1\n",
    "            if j < n:\n",
    "                return False\n",
    "            while i < m:\n",
    "                if not s[i].islower():\n",
    "                    return False\n",
    "                i += 1\n",
    "            return True\n",
    "        \n",
    "        ans = [check(s, pattern) for s in queries]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        def check(item, pattern):\n",
    "            i , j = 0 , 0\n",
    "            while j < len(pattern):\n",
    "                while i < len(item) and item[i] != pattern[j] and item[i].islower():\n",
    "                    #跳过不相同的item小写部分\n",
    "                    i += 1\n",
    "                if i == len(item) or item[i] != pattern[j]:\n",
    "                  #如果到字符串末尾,或大写字母不匹配\n",
    "                    return False\n",
    "                i += 1\n",
    "                j += 1\n",
    "\n",
    "            while i < len(item) and item[i].islower():\n",
    "                #跳过末尾的item小写部分\n",
    "                i += 1\n",
    "            return i == len(item)#如果在跳过末尾小写部分时遇到大写,则i!=len(item)\n",
    "        return [check(item, pattern) for item in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        queries_length = len(queries)\n",
    "        pattern_length = len(pattern)\n",
    "        answer_list = [False] * queries_length\n",
    "        for index in range(queries_length):\n",
    "            if isMatch(pattern, pattern_length, queries[index]):\n",
    "                answer_list[index] = True \n",
    "        return answer_list\n",
    "\n",
    "def isMatch(pattern, pattern_length, query):\n",
    "    query_length = len(query)\n",
    "    if query_length < pattern_length:\n",
    "        return False \n",
    "    query_pointer, pattern_pointer = 0, 0\n",
    "    while pattern_pointer < pattern_length and query_pointer < query_length:\n",
    "        if query[query_pointer] == pattern[pattern_pointer]:\n",
    "            query_pointer += 1\n",
    "            pattern_pointer += 1\n",
    "        elif query[query_pointer].isupper():\n",
    "            return False \n",
    "        else:\n",
    "            query_pointer += 1 \n",
    "    if pattern_pointer == pattern_length:\n",
    "        for letter in query[query_pointer:]:\n",
    "            if letter.isupper():\n",
    "                return False \n",
    "        return True \n",
    "    else:\n",
    "        return False \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def match(self,q:str,pat:str)->bool:\n",
    "        if len(q)<len(pat):\n",
    "            return False\n",
    "        i = 0\n",
    "        m = len(q)\n",
    "        for p in pat:\n",
    "            while i<m and q[i]!=p and q[i].islower():\n",
    "                i+=1\n",
    "            if i==m:\n",
    "                return False\n",
    "            if (p.isupper())!=(q[i].isupper()):\n",
    "                return False\n",
    "            i += 1\n",
    "        return all(c.islower() for c in q[i:])\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            res.append(self.match(q, pattern))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "\n",
    "\n",
    "        ans = []\n",
    "        n = len(pattern)\n",
    "        for q in queries:\n",
    "            m = len(q)\n",
    "            i = j = 0\n",
    "            while i < m and j < n:\n",
    "                if q[i] == pattern[j]:\n",
    "                    j += 1\n",
    "                elif q[i].isupper():\n",
    "                    break\n",
    "                i += 1\n",
    "            \n",
    "            if j == n:\n",
    "                if i < m:\n",
    "                    while i < m:\n",
    "                        if q[i].isupper():\n",
    "                            ans.append(False)\n",
    "                            break\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        ans.append(True)\n",
    "                else:\n",
    "                    ans.append(True)   \n",
    "            else:\n",
    "                ans.append(False)         \n",
    "        return ans\n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        \n",
    "        def cheack(q):\n",
    "            i,j=0,0\n",
    "            while i<len(q):\n",
    "                if j<len(pattern)and q[i]==pattern[j]:\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                elif q[i].isupper():\n",
    "                    return False\n",
    "                else:\n",
    "                    i+=1\n",
    "            return j==len(pattern)\n",
    "        res=[]\n",
    "        for q in queries:\n",
    "            res.append(cheack(q))\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        m = len(pattern)\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            n = len(q)\n",
    "            i = 0\n",
    "            j = 0\n",
    "            flag = False\n",
    "            while i < n and j < m:\n",
    "                # print(q[i])\n",
    "                if q[i] == pattern[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                    continue\n",
    "                if q[i].islower():\n",
    "                    i += 1\n",
    "                else:\n",
    "                    flag = True\n",
    "                    break\n",
    "\n",
    "            while i < n:\n",
    "                # print(q[i])\n",
    "                if not q[i].islower():\n",
    "                    flag = True\n",
    "                i += 1\n",
    "            # print(flag)\n",
    "            if j == m and not flag:\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        s = '(^[a-z]*' + '[a-z]*'.join(list(pattern)) + '[a-z]*$)'\n",
    "        pat = re.compile(s)\n",
    "        res = list(map(pat.match, queries))\n",
    "        return list(map(bool, res))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        \n",
    "        def helper(a, b):\n",
    "            i = 0\n",
    "            j = 0\n",
    "            while i < len(a) and j < len(b):\n",
    "                if a[i] == b[j]:\n",
    "                    i += 1\n",
    "                elif b[j].isupper():\n",
    "                    return False\n",
    "                j += 1\n",
    "            return i == len(a) and all(x.islower() for x in b[j:])\n",
    "        \n",
    "        return [helper(pattern, x) for x in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        def check(qu,pa):\n",
    "            lm = len(qu)\n",
    "            i = 0\n",
    "            ln = len(pa)\n",
    "            j = 0\n",
    "            while i < lm and j < ln:\n",
    "                print(i, j, qu[i], pa[j])\n",
    "                if qu[i] == pa[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                elif qu[i] != pa[j] and qu[i].islower():\n",
    "                    i += 1\n",
    "                elif qu[i] != pa[j] and qu[i].upper():\n",
    "                    return False\n",
    "            if j != ln:\n",
    "                return False\n",
    "            else:\n",
    "                print(i, qu[i:])\n",
    "                for x in qu[i:]:\n",
    "                    if x.isupper():\n",
    "                        return False\n",
    "            return True\n",
    "        # print([check(q, pattern) for q in queries])\n",
    "        return [check(q, pattern) for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        n = len(queries)\n",
    "        res = [True] * n\n",
    "        for i in range(n):\n",
    "            p = 0\n",
    "            for c in queries[i]:\n",
    "                if p < len(pattern) and pattern[p] == c:\n",
    "                    p += 1\n",
    "                elif c.isupper():\n",
    "                    res[i] = False\n",
    "                    break\n",
    "            if p < len(pattern):\n",
    "                res[i] = False\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        n = len(queries)\n",
    "        res = [True] * n\n",
    "        for i in range(n):\n",
    "            idx = 0\n",
    "            for char in queries[i]:\n",
    "                if idx < len(pattern) and char == pattern[idx]:\n",
    "                    idx += 1\n",
    "\n",
    "                elif char.isupper():\n",
    "                    res[i] = False\n",
    "                    break\n",
    "            \n",
    "            if idx != len(pattern):\n",
    "                res[i] = False\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # res = [True] * len(queries)\n",
    "        # for i in range(len(queries)):\n",
    "        #     idx = 0\n",
    "        #     for char in queries[i]:\n",
    "        #         if idx < len(pattern) and pattern[idx] == char:\n",
    "        #             idx += 1\n",
    "                \n",
    "        #         elif char.isupper():\n",
    "        #             res[i] = False\n",
    "        #             break\n",
    "                \n",
    "        #     if idx < len(pattern):\n",
    "        #         res[i] = False\n",
    "        \n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        lenp = len(pattern)\n",
    "        def check(s):\n",
    "            ls, lp, lens = 0, 0, len(s)\n",
    "            while ls < lens and lp < lenp:\n",
    "                if s[ls] == pattern[lp]: lp += 1\n",
    "                elif s[ls].isupper(): return False\n",
    "                ls += 1\n",
    "            return lp == lenp and len(list(filter(lambda x: x.isupper(), s[ls:]))) == 0\n",
    "\n",
    "        return [check(s) for s in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        lenp = len(pattern)\n",
    "        def check(s):\n",
    "            ls, lp, lens = 0, 0, len(s)\n",
    "            while ls < lens and lp < lenp:\n",
    "                if s[ls] == pattern[lp]: lp += 1\n",
    "                elif s[ls].isupper(): return False\n",
    "                ls += 1\n",
    "            return lp == lenp and len(list(filter(lambda x: x.isupper(), s[ls:]))) == 0\n",
    "\n",
    "        return [check(s) for s in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        def check(item, pattern):\n",
    "            i , j = 0 , 0\n",
    "            while j < len(pattern):\n",
    "                while i < len(item) and item[i] != pattern[j] and item[i].islower():\n",
    "                    #跳过不相同的item小写部分\n",
    "                    i += 1\n",
    "                if i == len(item) or item[i] != pattern[j]:\n",
    "                  #如果到字符串末尾,或大写字母不匹配\n",
    "                    return False\n",
    "                i += 1\n",
    "                j += 1\n",
    "\n",
    "            while i < len(item) and item[i].islower():\n",
    "                #跳过末尾的item小写部分\n",
    "                i += 1\n",
    "            return i == len(item)#如果在跳过末尾小写部分时遇到大写,则i!=len(item)\n",
    "        return [check(item, pattern) for item in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        lenp = len(pattern)\n",
    "        def check(s):\n",
    "            ls, lp, lens = 0, 0, len(s)\n",
    "            while ls < lens and lp < lenp:\n",
    "                if s[ls] == pattern[lp]: lp += 1\n",
    "                elif s[ls].isupper(): return False\n",
    "                ls += 1\n",
    "            return lp == lenp and len(list(filter(lambda x: x.isupper(), s[ls:]))) == 0\n",
    "\n",
    "        return [check(s) for s in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        def check(qu,pa):\n",
    "            lm = len(qu)\n",
    "            i = 0\n",
    "            ln = len(pa)\n",
    "            j = 0\n",
    "            while i < lm and j < ln:\n",
    "                print(i, j, qu[i], pa[j])\n",
    "                if qu[i] == pa[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                elif qu[i] != pa[j] and qu[i].islower():\n",
    "                    i += 1\n",
    "                elif qu[i] != pa[j] and qu[i].upper():\n",
    "                    return False\n",
    "            if j != ln:\n",
    "                return False\n",
    "            else:\n",
    "                for x in qu[i:]:\n",
    "                    if x.isupper():\n",
    "                        return False\n",
    "            return True\n",
    "        # print([check(q, pattern) for q in queries])\n",
    "        return [check(q, pattern) for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        p=r\"[a-z]*\"\n",
    "        m=r\"^\"+p+p.join(list(pattern))+p+r\"$\"\n",
    "        res=[]\n",
    "        for i in queries:\n",
    "            res.append(True if re.match(m,i) else False)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self,):\n",
    "        self.children = dict()\n",
    "        self.isEnd = False\n",
    "    \n",
    "    def insert(self, word: str) -> None:\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            if ch not in cur.children:\n",
    "                cur.children[ch] = Trie()\n",
    "            cur = cur.children[ch]\n",
    "        cur.isEnd = True\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            if not ch.isupper():\n",
    "                # 不匹配的小写字母跳过，这个操作很巧妙，不会移动cur\n",
    "                if ch not in cur.children:\n",
    "                    continue\n",
    "            else:\n",
    "                if ch not in cur.children:\n",
    "                    return False\n",
    "            cur = cur.children[ch]\n",
    "        return cur.isEnd\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:\n",
    "        # lenp = len(pattern)\n",
    "        # def check(s):\n",
    "        #     ls, lp, lens = 0, 0, len(s)\n",
    "        #     while ls < lens and lp < lenp:\n",
    "        #         if s[ls] == pattern[lp]: lp += 1\n",
    "        #         elif s[ls].isupper(): return False\n",
    "        #         ls += 1\n",
    "        #     return lp == lenp and len(list(filter(lambda x: x.isupper(), s[ls:]))) == 0\n",
    "        # return [check(s) for s in queries]\n",
    "        dict_tree = Trie()\n",
    "        dict_tree.insert(pattern)\n",
    "        return [dict_tree.search(query) for query in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def camelMatch(self, queries, pattern: str) :\n",
    "        return [re.match('[a-z]*'.join(['^']+list(pattern)+['$']),q) is not None for q in queries]\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
